#include <stdlib.h>

#include "algo.h"
#include "iterator.h"
#include "List.h"

struct ListNode {
	struct ListNode *next_;
	struct ListNode *prev_;
	int data_;
};

static ListNode *listNodeNew(int _data);

static void listNodeDelete(ListNode *_this);

static void listNodeConstruct(ListNode *_this, int _data);

static void listNodeDestruct(ListNode *_this);

static ListNode *listNodeNew(int _data) {
	ListNode *listNode = (ListNode *) malloc(sizeof(ListNode));
	listNodeConstruct(listNode, _data);
	return listNode;
}

static void listNodeDelete(ListNode *_this) {
	listNodeDestruct(_this);
	free(_this);
}

static void listNodeConstruct(ListNode *_this, int _data) {
	_this->next_ = NULL;
	_this->prev_ = NULL;
	_this->data_ = _data;
}

static void listNodeDestruct(ListNode *_this) {
}

static bool listIteratorConstruct(ListIterator *_this, ListNode *_listNode);

static bool listIteratorConstruct(ListIterator *_this, ListNode *_listNode) {
	_this->listNode_ = _listNode;
	return true;
}

bool listIteratorEqualTo(const ListIterator *_this, const ListIterator *_listIterator) {
	return _this->listNode_ == _listIterator->listNode_;
}

bool listIteratorNotEqualTo(const ListIterator *_this, const ListIterator *_listIterator) {
	return _this->listNode_ != _listIterator->listNode_;
}

int *listIteratorIndirect(const ListIterator *_this) {
	return &_this->listNode_->data_;
}

ListIterator *listIteratorIncreasePrefix(ListIterator *_this) {
	_this->listNode_ = _this->listNode_->next_;
	return _this;
}

ListIterator listIteratorIncreasePostfix(ListIterator *_this) {
	ListIterator temp = *_this;
	listIteratorIncreasePrefix(_this);
	return temp;
}

ListIterator *listIteratorDecreasePrefix(ListIterator *_this) {
	_this->listNode_ = _this->listNode_->prev_;
	return _this;
}

ListIterator listIteratorDecreasePostfix(ListIterator *_this) {
	ListIterator temp = *_this;
	listIteratorDecreasePrefix(_this);
	return temp;
}

static void listTransfer(ListIterator _position, ListIterator _first, ListIterator _last);

List *listNew() {
	List *list = (List *) malloc(sizeof(List));
	listConstruct(list);
	return list;
}

void listDelete(List *_this) {
	listDestruct(_this);
	free(_this);
}

void listConstruct(List *_this) {
	_this->listNode_ = listNodeNew(0);
	_this->listNode_->prev_ = _this->listNode_;
	_this->listNode_->next_ = _this->listNode_;
}

void listDestruct(List *_this) {
	listClear(_this);
	listNodeDelete(_this->listNode_);
}

ListIterator listBegin(const List *_this) {
	ListIterator listIterator;
	listIteratorConstruct(&listIterator, _this->listNode_->next_);
	return listIterator;
}

ListIterator listEnd(const List *_this) {
	ListIterator listIterator;
	listIteratorConstruct(&listIterator, _this->listNode_);
	return listIterator;
}

bool listInsert(ListIterator _position, int _data) {
	ListNode *listNode = listNodeNew(_data);
	if (listNode == NULL) {
		return false;
	}
	listNode->prev_ = _position.listNode_->prev_;
	listNode->prev_->next_ = listNode;
	listNode->next_ = _position.listNode_;
	listNode->next_->prev_ = listNode;
	return true;
}

bool listInsertN(ListIterator _position, size_t _n, int _value) {
	for (; _n > 0; --_n) {
		if (!listInsert(_position, _value)) {
			return false;
		}
	}
	return true;
}

bool listInsertIn(ListIterator _position, ListIterator _first, ListIterator _last) {
	for (; !listIteratorEqualTo(&_first, &_last); listIteratorIncreasePrefix(&_first)) {
		if (!listInsert(_position, *listIteratorIndirect(&_first))) {
			return false;
		}
	}
	return true;
}

void listErase(ListIterator _position) {
	_position.listNode_->prev_->next_ = _position.listNode_->next_;
	_position.listNode_->next_->prev_ = _position.listNode_->prev_;
	listNodeDelete(_position.listNode_);
}

void listEraseN(ListIterator _position, size_t _n) {
	ListIterator next = _position;
	ListIterator prev = *listIteratorDecreasePrefix(&_position);
	for (; _n > 0; --_n) {
		listNodeDelete(listIteratorIncreasePostfix(&next).listNode_);
	}
	prev.listNode_->next_ = next.listNode_;
	next.listNode_->prev_ = prev.listNode_;
}

void listEraseIn(ListIterator _first, ListIterator _last) {
	_first.listNode_->prev_->next_ = _last.listNode_;
	_last.listNode_->prev_ = _first.listNode_->prev_;
	while (!listIteratorEqualTo(&_first, &_last)) {
		listNodeDelete(listIteratorIncreasePostfix(&_first).listNode_);
	}
}

void listSplice(ListIterator _position, ListIterator _listIterator) {
	listSpliceIn(_position, _listIterator, *listIteratorIncreasePrefix(&_listIterator));
}

void listSpliceN(ListIterator _position, ListIterator _listIterator, size_t _n) {
	ListIterator last = _listIterator;
	for (; _n > 0; --_n) {
		listIteratorIncreasePrefix(&last);
	}
	listSpliceIn(_position, _listIterator, last);
}

void listSpliceIn(ListIterator _position, ListIterator _first, ListIterator _last) {
	listTransfer(_position, _first, _last);
}

bool listEmpty(const List *_this) {
	ListIterator begin = listBegin(_this);
	ListIterator end = listEnd(_this);
	return listIteratorEqualTo(&begin, &end);
}

size_t listSize(const List *_this) {
	return distance(List, listBegin(_this), listEnd(_this));
}

void listClear(const List *_this) {
	listEraseIn(listBegin(_this), listEnd(_this));
}

ListIterator listMarge(ListIterator _first1, ListIterator _last1, ListIterator _first2, ListIterator _last2) {
	ListIterator first = *listIteratorIndirect(&_first1) < *listIteratorIndirect(&_first2) ? _first1 : _first2;
	while (!listIteratorEqualTo(&_first1, &_last1)) {
		ListIterator listIterator = loopUpperBound(List, _first2, _last2, *listIteratorIndirect(&_first1));
		if (listIteratorEqualTo(&listIterator, &_first2)) {
			listIteratorIncreasePrefix(&_first1);
		}
		else if (listIteratorEqualTo(&listIterator, &_last2)) {
			break;
		}
		else {
			listSpliceIn(_first1, _first2, listIterator);
			_first2 = listIterator;
		}
	}
	listSpliceIn(_first1, _first2, _last2);
	return first;
}

ListIterator listSort(ListIterator _first, ListIterator _last) {
	ListIterator center = center(List, _first, _last);
	if (listIteratorEqualTo(&center, &_first)) {
		return _first;
	}
	_first = listSort(_first, center);
	center = listSort(center, _last);
	return listMarge(_first, center, center, _last);
}

static void listTransfer(ListIterator _position, ListIterator _first, ListIterator _last) {
	if (listIteratorEqualTo(&_position, &_first) || listIteratorEqualTo(&_position, &_last) || listIteratorEqualTo(&_first, &_last)) {
		return;
	}
	ListNode *listNode = _first.listNode_->prev_;
	_first.listNode_->prev_ = _position.listNode_->prev_;
	_first.listNode_->prev_->next_ = _first.listNode_;
	_last.listNode_->prev_->next_ = _position.listNode_;
	_position.listNode_->prev_ = _last.listNode_->prev_;
	listNode->next_ = _last.listNode_;
	_last.listNode_->prev_ = listNode;
}
